//#pragma once
//
//#include <vector>
//#include <array>
//#include <queue>
//#include <cfloat>
//#include <cassert>
//#include "mltree/entry-1.hpp"
//#include <stdexcept>
//
//namespace MetricSpaceBenchmark::MLIndex::mltree {
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
//    template<typename T, int NROUTES = 4, int LEAFCAP = 50>
//    class MTreeNode {
//    protected:
//        MTreeNode<T, NROUTES, LEAFCAP> *parent;
//        int rindex{};
//
//    public:
//        MTreeNode() : parent(nullptr) {}
//
//        virtual ~MTreeNode() = default;
//
//        [[nodiscard]] virtual int size() const = 0;
//
//        [[nodiscard]] virtual bool isFull() const = 0;
//
//        [[nodiscard]] bool isRoot() const;
//
//        MTreeNode<T, NROUTES, LEAFCAP> *GetParentNode(int &rdx) const;
//
//        void SetParentNode(MTreeNode<T, NROUTES, LEAFCAP> *parentNode, int rdx);
//
//        virtual void SetChildNode(MTreeNode<T, NROUTES, LEAFCAP> *child, int rdx) = 0;
//
//        virtual MTreeNode<T, NROUTES, LEAFCAP> *GetChildNode(int rdx) const = 0;
//
//        virtual void Clear() = 0;
//    };
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    template<typename T, int NROUTES, int LEAFCAP>
//    class MTreeInternal : public MTreeNode<T, NROUTES, LEAFCAP> {
//    public:
//        int n_routeObjects;   // 当前节点存储的路由数目
//        RoutingObject<T> routeObjects[NROUTES];   // 存储路由对象的数组, 大小为 NROUTES
//
//    public:
//        MTreeInternal();
//
//        ~MTreeInternal() = default;
//
//        [[nodiscard]] int size() const {
//            return n_routeObjects;
//        }
//
//        [[nodiscard]] bool isFull() const {
//            return (n_routeObjects >= NROUTES);
//        }
//
//        /*
//         * 获取当前节点的所有路由对象,并将它们存入传入的 std::vector<RoutingObject<T>> 容器中.这个方法通常用于遍历或查询所有路由对象
//         */
//        void GetRoutes(std::vector<RoutingObject<T>> &Routes) const;
//
//        /*
//         * 选择一个路由对象进行插入操作或其他修改操作.
//         * @nobj 是需要插入或修改的对象
//         * @robj 是选定的路由对象
//         * @insert 标志是否为插入操作
//         * 通常,这个方法会根据 nobj 和现有路由对象的覆盖半径、距离等属性选择一个适合的路由对象
//         * return: 最优的路由对象及其下标位置
//         */
//        int SelectRoute(T nobj, RoutingObject<T> &robj, bool insert);
//
//        /*
//         * 选择多个路由对象,通常用于查询操作.
//         * @query 是查询对象
//         * @radius 是查询的半径
//         * @nodes 是一个队列,存储选择的子节点
//         * 该方法基于查询半径选择适当的子节点进行后续的查询
//         */
//        void SelectRoutes(T query, double radius, std::queue<MTreeNode<T, NROUTES, LEAFCAP> *> &nodes) const;
//
//        int StoreRoute(const RoutingObject<T> &robj);
//
//        void ConfirmRoute(const RoutingObject<T> &robj, int rdx) {
//            assert(rdx >= 0 && rdx < NROUTES && robj.subtree != nullptr);
//            routeObjects[rdx] = robj;
//        }
//
//        void GetRoute(int rdx, RoutingObject<T> &route) {
//            assert(rdx >= 0 && rdx < NROUTES);
//            route = routeObjects[rdx];
//        }
//
//        void SetChildNode(MTreeNode<T, NROUTES, LEAFCAP> *child, int rdx) {
//            assert(rdx >= 0 && rdx < NROUTES);
//            routeObjects[rdx].subtree = child;
//            child->SetParentNode(this, rdx);
//        }
//
//        MTreeNode<T, NROUTES, LEAFCAP> *GetChildNode(int rdx) const {
//            assert(rdx >= 0 && rdx < NROUTES);
//            return (MTreeNode<T, NROUTES, LEAFCAP> *) routeObjects[rdx].subtree;
//        }
//
//        void Clear() { n_routeObjects = 0; }
//
//    };
//
//    // 学习索引节点 ILM
//    template<typename T, int NROUTES = 4>
//    class ILMNode {
//    protected:
//        LinearModel<T> lm;  // 线性模型
//        T p;  // 枢轴点
//        int n_routeObjects;   // 当前节点存储的路由数目
//        ILMEntry<T> routeObjects[NROUTES];  // 条目数组
//    public:
//        ILMNode(const T &pivot) : p(pivot) {}
//
//        // 存储一个条目
//        int StoreEntry(const ILMEntry<T> &entry) {
//            assert(n_routeObjects < NROUTES);
//
//            int index = -1;
//            for (int i = 0; i < NROUTES; i++) {
//                if (routeObjects[i].ptr == nullptr) {
//                    routeObjects[i] = entry;
//                    index = i;
//                    n_routeObjects++;
//                    break;
//                }
//            }
//            return index;
//        }
//
//        // 获取条目
//        void GetRoute(int rdx, ILMEntry<T> &route) {
//            assert(rdx >= 0 && rdx < NROUTES);
//            route = routeObjects[rdx];
//        }
//    };
//
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    template<typename T, int NROUTES, int LEAFCAP>
//    class MTreeLeaf : public MTreeNode<T, NROUTES, LEAFCAP> {
//    public:
//        std::vector<DBEntry<T>> entries;
//
//    public:
//        MTreeLeaf() = default;
//
//        ~MTreeLeaf() { entries.clear(); }
//
//        [[nodiscard]] int size() const { return entries.size(); }
//
//        [[nodiscard]] bool isFull() const { return (entries.size() >= LEAFCAP); }
//
//        int StoreEntry(const DBEntry<T> &nobj);
//
//        void GetEntries(std::vector<DBEntry<T>> &dbentries) const;
//
//        void SelectEntries(T query, double radius, std::vector<Entry<T>> &results) const;
//
//        int DeleteEntry(const T &entry);
//
//        void SetChildNode(MTreeNode<T, NROUTES, LEAFCAP> *child, int rdx) {}
//
//        MTreeNode<T, NROUTES, LEAFCAP> *GetChildNode(int rdx) const { return nullptr; }
//
//        void Clear() { entries.clear(); }
//    };
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    // 学习叶节点 LLM
//    template<typename T, int NROUTES, int LEAFCAP>
//    class LLMNode : public MTreeNode<T, NROUTES, LEAFCAP> {
//    protected:
//        LinearModel<T> lm;  // 线性模型
//        T p;  // 枢轴点
//        std::vector<DBEntry<T>> entries;  // 条目数组
//    public:
//        LLMNode() = default;
//
//        ~LLMNode() {
//            entries.clear();
//        }
//
//        LLMNode(const T &pivot) : p(pivot) {}
//
//        // 存储一个条目
//        void StoreEntry(const DBEntry<T> &entry) {
//            if (entries.size() >= LEAFCAP) {
//                throw std::out_of_range("LLMNode is full");
//            }
//            entries.push_back(entry);
//        }
//
//        // 获取条目数组
//        void GetEntries(std::vector<DBEntry<T>> &llmentries) const {
//            for (const auto &e: entries) {
//                llmentries.push_back(e);
//            }
//        }
//
//        [[nodiscard]] int size() const {
//            return entries.size();
//        }
//
//        [[nodiscard]] bool isFull() const {
//            return (entries.size() >= LEAFCAP);
//        }
//
//        // 借助线性模型进行选择---待定
//        void SelectEntries(T query, double radius, std::vector<Entry<T>> &results) const;
//
//        int DeleteEntry(const T &entry);
//
//        void SetChildNode(MTreeNode<T, NROUTES, LEAFCAP> *child, int rdx) {}
//
//        MTreeNode<T, NROUTES, LEAFCAP> *GetChildNode(int rdx) const { return nullptr; }
//
//        void Clear() {
//            entries.clear();
//        }
//    };
//
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    template<typename Element, typename T, int NROUTES, int LEAFCAP>
//    class CustomPriorityQueue {
//    private:
//        std::vector<Element> heap;
//    public:
//        // 插入元素
//        void push(const Element &e) {
//            heap.push_back(e);
//            std::push_heap(heap.begin(), heap.end(), std::greater<Element>());
//        }
//
//        // 查找元素
//        typename std::vector<Element>::iterator find(const Element &target) {
//            return std::find(heap.begin(), heap.end(), target);
//        }
//
//        // 获取堆顶元素
//        const Element &top() const {
//            if (heap.empty()) {
//                throw std::out_of_range("Heap is empty");
//            }
//            return heap.front();
//        }
//
//        [[nodiscard]] bool empty() const {
//            return heap.empty();
//        }
//
//        // 删除特定元素
//        void erase(const Element &target) {
//            auto it = find(target);
//            if (it != heap.end()) {
//                // 替换要删除的元素与堆顶元素
//                *it = heap.back();
//                heap.pop_back();
//                // 调整堆
//                std::make_heap(heap.begin(), heap.end(), std::greater<Element>());
//            }
//        }
//
//        void pop() {
//            if (heap.empty()) {
//                throw std::out_of_range("Heap is empty");
//            }
//            std::pop_heap(heap.begin(), heap.end(), std::greater<Element>());
//            heap.pop_back();
//        }
//
//        // 添加begin和end函数
//        typename std::vector<Element>::iterator begin() {
//            return heap.begin();
//        }
//
//        typename std::vector<Element>::iterator end() {
//            return heap.end();
//        }
//    };
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    template<typename T, int NROUTES, int LEAFCAP>
//    void MTreeNode<T, NROUTES, LEAFCAP>::SetParentNode(MTreeNode<T, NROUTES, LEAFCAP> *parentNode, const int rdx) {
//        assert(rdx >= 0 && rdx < NROUTES);
//        parent = parentNode;
//        rindex = rdx;
//    }
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    /**
//     *  MTreeInternal Node implementation
//     **/
//    template<typename T, int NROUTES, int LEAFCAP>
//    MTreeInternal<T, NROUTES, LEAFCAP>::MTreeInternal() {
//        n_routeObjects = 0;
//        for (int i = 0; i < NROUTES; i++) {
//            routeObjects[i].subtree = nullptr;
//        }
//    }
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    template<typename T, int NROUTES, int LEAFCAP>
//    void MTreeInternal<T, NROUTES, LEAFCAP>::GetRoutes(std::vector<RoutingObject<T>> &Routes) const {
//        for (int i = 0; i < NROUTES; i++) {
//            if (routeObjects[i].subtree != nullptr)
//                Routes.push_back(routeObjects[i]);
//        }
//    }
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    /*
//     * 选择一个路由对象进行插入操作或者其他修改操作.
//     * @nobj 是需要插入或修改的对象
//     * @robj 是选定的路由对象
//     * @insert 标志是否为插入操作
//     * 通常,这个方法会根据 nobj 和现有路由对象的覆盖半径、距离等属性选择一个适合的路由对象
//     * return: 最优的路由对象及其下标位置
//     */
//    template<typename T, int NROUTES, int LEAFCAP>
//    int MTreeInternal<T, NROUTES, LEAFCAP>::SelectRoute(const T nobj, RoutingObject<T> &robj, bool insert) {
//        int min_pos = -1;
//        auto min_dist = DBL_MAX;
//        for (int i = 0; i < NROUTES; i++) {
//            if (routeObjects[i].subtree != nullptr) {
//                const double d = routeObjects[i].distance(nobj); //distance(routes[i].key, nobj.key);
//                if (d < min_dist) {
//                    min_pos = i;
//                    min_dist = d;
//                }
//            }
//        }
//
//        if (min_pos < 0)
//            throw std::logic_error("unable to find route entry");
//
//        /*
//         * 更新覆盖半径: 如果当前操作是插入(insert 为 true), 并且找到的最小距离大于当前路由对象的覆盖半径,
//         * 则更新该路由对象的覆盖半径为 min_dist(扩大圆).覆盖半径用于定义路由对象的影响范围,确保新插入的对象仍在当前路由对象的覆盖范围内
//         */
//        if (insert && min_dist > routeObjects[min_pos].cover_radius)
//            routeObjects[min_pos].cover_radius = min_dist;
//
//        // 将选择的路由对象 routeObjects[min_pos] 赋值给传入的 robj 引用.调用此函数后, robj 就保存了最优的路由对象
//        robj = routeObjects[min_pos];
//
//        return min_pos;
//    }
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    /*
//     * 选择多个路由对象,通常用于查询操作.
//     * @query 是查询对象
//     * @radius 是查询的半径
//     * @nodes 是一个队列,存储选择的子节点.
//     * 该方法基于查询半径选择适当的子节点进行后续的查询
//     */
//    template<typename T, int NROUTES, int LEAFCAP>
//    void MTreeInternal<T, NROUTES, LEAFCAP>::SelectRoutes(const T query, const double radius,
//                                                          std::queue<MTreeNode<T, NROUTES, LEAFCAP> *> &nodes) const {
//
//        double d = 0;
//        if (this->parent != nullptr) {
//            RoutingObject<T> pobj;
//            ((MTreeInternal<T, NROUTES, LEAFCAP> *) this->parent)->GetRoute(this->rindex, pobj);
//            d = pobj.distance(query);
//        }
//
//        for (int i = 0; i < NROUTES; i++) {
//            if (routeObjects[i].subtree != nullptr) {
//                if (abs(d - routeObjects[i].dis) <= radius + routeObjects[i].cover_radius) {
//                    if (routeObjects[i].distance(query) <=
//                        radius + routeObjects[i].cover_radius) {   //distance(routes[i].key, query)
//                        nodes.push((MTreeNode<T, NROUTES, LEAFCAP> *) routeObjects[i].subtree);
//                    }
//                }
//            }
//        }
//    }
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    template<typename T, int NROUTES, int LEAFCAP>
//    int MTreeInternal<T, NROUTES, LEAFCAP>::StoreRoute(const RoutingObject<T> &robj) {
//        assert(n_routeObjects < NROUTES);
//
//        int index = -1;
//        for (int i = 0; i < NROUTES; i++) {
//            if (routeObjects[i].subtree == nullptr) {
//                routeObjects[i] = robj;
//                index = i;
//                n_routeObjects++;
//                break;
//            }
//        }
//        return index;
//    }
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    /**
//     * MTreeLeaf<T,NROUTES,LEAFCAP> node implementation
//     **/
//
//    template<typename T, int NROUTES, int LEAFCAP>
//    int MTreeLeaf<T, NROUTES, LEAFCAP>::StoreEntry(const DBEntry<T> &nobj) {
//        if (entries.size() >= LEAFCAP)
//            throw std::out_of_range("full leaf node");
//
//        int index = entries.size();
//        entries.push_back(nobj);
//        return index;
//    }
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    template<typename T, int NROUTES, int LEAFCAP>
//    void MTreeLeaf<T, NROUTES, LEAFCAP>::GetEntries(std::vector<DBEntry<T>> &dbentries) const {
//        for (auto &e: entries) {
//            dbentries.push_back(e);
//        }
//    }
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    template<typename T, int NROUTES, int LEAFCAP>
//    void MTreeLeaf<T, NROUTES, LEAFCAP>::SelectEntries(const T query, const double radius,
//                                                       std::vector<Entry<T>> &results) const {
//        double d = 0;
//        if (this->parent != nullptr) {
//            RoutingObject<T> pobj;
//            ((MTreeInternal<T, NROUTES, LEAFCAP> *) this->parent)->GetRoute(this->rindex, pobj);
//            d = pobj.distance(query);               //distance(pobj.key, query);
//        }
//
//        for (int j = 0; j < (int) entries.size(); j++) {
//            if (abs(d - entries[j].dis) <= radius) {
//                if (entries[j].distance(query) <= radius) {    //distance(entries[j].key, query) <= radius){
//                    results.push_back({entries[j].id, entries[j].key});
//                }
//            }
//        }
//    }
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//    template<typename T, int NROUTES, int LEAFCAP>
//    int MTreeLeaf<T, NROUTES, LEAFCAP>::DeleteEntry(const T &entry) {
//        int count = 0;
//
//        double d = 0;
//        if (this->parent != nullptr) {
//            RoutingObject<T> pobj;
//            ((MTreeInternal<T, NROUTES, LEAFCAP> *) this->parent)->GetRoute(this->rindex, pobj);
//            d = pobj.key.distance(entry.key);
//        }
//
//        for (int j = 0; j < (int) entries.size(); j++) {
//            if (d == entries[j].dis) {
//                if (entry.distance(entries[j].key) == 0) {
//                    entries[j] = entries.back();
//                    entries.pop_back();
//                    count++;
//                }
//            }
//        }
//
//        return count;
//    }
//
//    template<typename T, int NROUTES, int LEAFCAP>
//    int LLMNode<T, NROUTES, LEAFCAP>::DeleteEntry(const T &entry) {
//        int count = 0;
//
//        double d = 0;
//        if (this->parent != nullptr) {
//            RoutingObject<T> pobj;
//            ((MTreeInternal<T, NROUTES, LEAFCAP> *) this->parent)->GetRoute(this->rindex, pobj);
//            d = pobj.key.distance(entry.key);
//        }
//
//        for (int j = 0; j < (int) entries.size(); j++) {
//            if (d == entries[j].dis) {
//                if (entry.distance(entries[j].key) == 0) {
//                    entries[j] = entries.back();
//                    entries.pop_back();
//                    count++;
//                }
//            }
//        }
//
//        return count;
//    }
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//}
//
//
